/**
 * Exercise 9.56
 * -----------------------------------------------------------------------------
 * Give the binomial queue that results when the keys `E A S Y Q U E S T I O N`
 * are inserted into an initially empty binomial queue.
 * -----------------------------------------------------------------------------
 */
#include <assert.h>
#include <stdlib.h>

typedef char Item;
typedef struct PQnode* PQlink;
typedef struct pq* PQ;

struct PQnode {
    Item key;
    PQlink l;
    PQlink r;
};

struct pq {
    PQlink *bq;
};

#define maxBQsize 4
#define test(C, B, A) 4*(C) + 2*(B) + 1*(A)

static PQlink z = NULL;

/////////////////////////////////接口操作////////////////////////////////////
PQ PQinit();
PQlink PQinsert(PQ pq, Item v);


///////////////////////////////////辅助函数/////////////////////////////////
PQlink pair(PQlink p, PQlink q);

//////////////////////////////////测试用例/////////////////////////////////
void test_insert();

int main(int argc, char *argv[]) {
    test_insert();
    return 0;
}

PQ PQinit() {
    PQ pq = (PQ)malloc(sizeof(*pq));
    pq->bq = (PQlink *)malloc(maxBQsize * sizeof(PQlink));

    int i;
    for (i = 0; i < maxBQsize; i++) {
        pq->bq[i] = z;
    }

    return pq;
}

PQlink PQinsert(PQ pq, Item v) {
    PQlink t = malloc(sizeof(*t));
    PQlink c = t;
    c->key = v;
    c->l = z;
    c->r = z;
    int i;

    for (i = 0; i < maxBQsize; i++) {
        if (c == z) {
            break;
        }
        if (pq->bq[i] == z) {
            pq->bq[i] = c;
            break;
        }
        c = pair(c, pq->bq[i]);
        pq->bq[i] = z;

    }

    return t;
}

PQlink pair(PQlink p, PQlink q) {
    if (p->key < q->key) {
        p->r = q->l;
        q->l = p;
        return q;
    }else {
        q->r = p->l;
        p->l = q;
        return p;
    }
}

void test_insert() {
    PQ pq = PQinit();
    // E-A-S-Y-Q-U-E-S-T-I-O-N
    PQinsert(pq, 'E');
    PQinsert(pq, 'A');
    PQinsert(pq, 'S');
    PQinsert(pq, 'Y');
    PQinsert(pq, 'Q');
    PQinsert(pq, 'U');
    PQinsert(pq, 'E');
    PQinsert(pq, 'S');
    PQinsert(pq, 'T');
    PQinsert(pq, 'I');
    PQinsert(pq, 'O');
    PQinsert(pq, 'N');

    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2]->key == 'T');
    assert(pq->bq[2]->r == z);
    assert(pq->bq[2]->l->key == 'O');
    assert(pq->bq[2]->l->l->key == 'N');
    assert(pq->bq[2]->l->r->key == 'I');
    assert(pq->bq[3]->key == 'Y');
    assert(pq->bq[3]->r == z);
    assert(pq->bq[3]->l->key == 'U');
    assert(pq->bq[3]->l->l->key == 'S');
    assert(pq->bq[3]->l->r->key == 'E');
    assert(pq->bq[3]->l->l->l->key == 'E');
    assert(pq->bq[3]->l->l->r->key == 'Q');
    assert(pq->bq[3]->l->r->l->key == 'A');
    assert(pq->bq[3]->l->r->r->key == 'S');
}